package com.chunsoft.sort;

import static com.chunsoft.sort.SortUtils.*;
import static com.chunsoft.sort.SortUtils.printArray;

/**
 * Title: MergeSort_SmallSum.java
 * Description: 小和问题
 * 在一个数组中，一个数左边比它小的数的总和，叫数的小和，所有数的小和累加起来，叫数组小和。求数组小和？
 * Create DateTime: 2023/11/30 21:33
 *
 * @author chunsoft
 */
public class MergeSortSmallSum {
    public static int smallSum(int[] arr) {

        if (arr == null || arr.length < 2) {
            return 0;
        }

        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int l, int r) {

        if (l == r) {
            return 0;
        }

        int mid = l + ((r - l) >> 1);

        return process(arr, l, mid)
                + process(arr, mid + 1, r)
                + merge(arr, l, mid, r);
    }

    private static int merge(int[] arr, int l, int mid, int r) {
        int[] help = new int[r - l + 1];
        int i = 0, res = 0, p1 = l, p2 = mid + 1;

        while (p1 <= mid && p2 <= r) {
            res += arr[p1] < arr[p2] ? ((r - p2) + 1) * arr[p1] : 0;
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }

        while(p1 <= mid) {
            help[i++] = arr[p1++];
        }
        
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }

        for (i = 0;  i < help.length; i++) {
            arr[l + i] = help[i];
        }

        return res;
    }

    public static void main(String[] args) {
        int testTime = 5;
        int maxSize = 100;
        int maxValue = 100;
        int res = 0;
        boolean succeed = true;
        for (int i = 0; i < testTime; i++) {
            int[] arr1 = generateRandomArray(maxSize, maxValue);
            printArray(arr1);
            int[] arr2 = copyArray(arr1);
            res = smallSum(arr1);
            comparator(arr2);
            if (!isEqual(arr1, arr2)) {
                succeed = false;
                printArray(arr1);
                printArray(arr2);
                break;
            }
            printArray(arr1);
            System.out.println("小和结果：" + res);
        }
        System.out.println("验证结果：" + succeed);
    }
}
